# -*- coding: utf-8 -*-

''' 
Autores: 
Pedro Godinho - 6355
Pedro Lopes - 9850
'''

import sys
import math
from random import uniform
from random import shuffle
from time import clock
import matplotlib.pyplot as plt

''' Class responsable for CombSort algorithm and tests'''
class CombSort:

    '''@param A: list to sort'''
    def combsort(self,A):
            
        n = len(A)
        swapped = True
        
        while n > 1 or swapped == True:
            n = max(1, int(n / 1.3))
            swapped = False
            
            for i in range(len(A) - n):
                j = i + n
                
                if A[i] > A[j]:
                    A[i], A[j] = A[j], A[i]
                    swapped = True

    def grafico(self):
        Z = [1] + range(50, 1050, 50)
        T = []
        M = 25
        for n in Z:
            A = [ uniform(0.0,1.0) for k in xrange(n)]
            shuffle(A)
            tempos = []
            for k in range(M):
                t1 = clock()
                self.combsort(A)
                t2 = clock()
                tempos.append(t2-t1)
            media = reduce(lambda x, y: x + y, tempos) / len(tempos)
            var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
        
            T.append((n,media, var))

        X = [n for n, media, var in T]
        Y = [media for n, media, var in T]
        ct = 10e5
        Z = [ (n * (math.log(n)))/ct for n, media, var in T]


        plt.grid(True)
        plt.ylabel(u'T(n) - tempo de execução médio em segundos')
        plt.xlabel(u'n - número de elementos')
        plt.plot(X,Y,'rs', label="resultado experimental")
        plt.plot(X, Z, 'b^', label=u"previsão teórica")
        plt.title("Comb Sort")
        plt.legend()
        plt.show()
